
"""
二叉树的前序、中序、后序遍历
https://leetcode.cn/problems/binary-tree-postorder-traversal/

"""

from typing import Optional, List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:

    def inorder_recursion(self, root: Optional[TreeNode], res: List) -> List[int]:
        """
        中序遍历，递归
        :param root:
        :return:
        """
        if root:
            self.inorder_recursion(root.left, res)
            res.append(root.val)
            self.inorder_recursion(root.right, res)

        return res

    def preorder_recursion(self, root: Optional[TreeNode], res: List) -> List[int]:
        """
        先序遍历，递归
        :param root:
        :param res:
        :return:
        """
        if root:
            res.append(root.val)
            self.preorder_recursion(root.left, res)
            self.preorder_recursion(root.right, res)

        return res

    def postorder_recursion(self, root: Optional[TreeNode], res: List) -> List[int]:
        """
        后序遍历，递归
        :param root: 
        :param res: 
        :return: 
        """
        if root:
            self.postorder_recursion(root.left, res)
            self.postorder_recursion(root.right, res)
            res.append(root.val)

        return res

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        中序遍历
        :param root:
        :return:
        """
        # 递归法
        res = []
        res = self.inorder_recursion(root, res)
        return res

    def preOrderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        先序遍历
        :param root: 
        :return: 
        """
        # 递归法
        res = []
        res = self.preorder_recursion(root, res)
        return res

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        后序遍历
        :param root: 
        :return: 
        """
        # 递归法
        res = []
        res = self.postorder_recursion(root, res)
        return res
